package heapsort;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Random;

public class ConsumerHeap {

    static int count = 0;

    @Test
    public void client() {
        Random random = new Random(1);
        for (int i = 0; i < 500000; i++) {
            /**
             * 随机样本长度
             */
            int anInt = random.nextInt(100) + 1;
            int[] arr = new int[anInt];
            for (int j = 0; j < anInt; j++) {
                /**
                 * 随机样本数据
                 */
                arr[j] = random.nextInt(100);
            }
            System.out.println("=======================第" + (i + 1) + "次=======================");
            consumerHeap consumerHeap = new consumerHeap(true, arr);
            consumerHeap.sorted();
            System.out.print("算法排序后==》");
            for (int i1 = 0; i1 < arr.length; i1++) {
                System.out.print(consumerHeap.poll());
                System.out.print(" ");
            }
            System.out.println();
            boolean logarithmizer = logarithmizer(arr, consumerHeap);
            if (logarithmizer) {
                System.out.println("对数器验证结果：PASS");
            } else {
                System.out.println("对数器验证结果：NOT PASS");
            }
        }

        System.out.println("==============================================");
        System.out.println("=======                                 ======");
        System.out.println("=======    验证不通过结果为：" + count +"   ======");
        System.out.println("=======                                 ======");
        System.out.println("==============================================");
    }

    @Test
    public void client1() {
        int[] arr = {5,7,5,5,8,3,2,1};
        // java默认提供的小根堆结构
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int j : arr) {
            pq.add(j);
        }
        for (int j : arr) {
            System.out.print(pq.poll());
            System.out.print(" ");
        }
    }

    /**
     * 自定义堆结构
     */
    private static class consumerHeap {
        // 堆的初始容量
        private int heapSize = 7;
        // 自定义堆结构底层使用数据实现
        private final int[] heap;
        // 添加数据的时候，使用的临时变量，防止数组越界
        private int index = 0;
        // 弹出数据的时候，使用的临时变量，防止数组越界
        private int count = 0;
        // true-大根堆，false-小根堆
        private boolean flag = true;

        /**
         * 构造函数
         * @param heapSize 初始化时，必须指定堆的大小
         * @param flag true-大根堆，false-小根堆
         */
        public consumerHeap(int heapSize, boolean flag) {
            this.heapSize = heapSize;
            this.flag = flag;
            heap = new int[heapSize];
        }

        /**
         * 构造函数
         * @param flag true-大根堆，false-小根堆
         * @param arr 初始化时，传入指定的数组，将数组转化成堆
         */
        public consumerHeap(boolean flag, int[] arr) {
            this.heapSize = arr.length;
            this.flag = flag;
            heap = new int[heapSize];
            for (int j : arr) {
                push(j);
            }
        }

        /**
         * 单个添加数据
         * @param value 数据
         */
        public void push(int value) {
            if (index == heapSize) {
                throw new IllegalStateException("Heap Size is overflow");
            }

            // 将数据直接添加到index位置
            heap[index] = value;
            // 进行调整
            heapfy(heap, index++);
        }

        public int poll () {
            if (count == heapSize) {
                count = 0;
            }
            return heap[count++];
        }

        /**
         * 堆排序：
         * 1、对于大根堆来说，最顶端位置上的数据就是整个堆中最大的数据，利用这个特点，
         * 每次将这个最顶端的数据和堆最后边位置上的数据交换后，堆的小大减1，并且将0至减1后的
         * 堆上的数据重新进行大根堆的调整，调整后继续之前的操作，直到交换的位置到达0为止，也就是
         * 堆大小一直减1减到0为止。此时，堆中的数据就变成了有序的数，而且是升序的。
         * 2、对于小根堆来说，最顶端位置上的数据就是整个堆中最小的数据，利用这个特点，
         * 每次将这个最顶端的数据和堆最后边位置上的数据交换后，堆的小大减1，并且将0至减1后的
         * 堆上的数据重新进行小根堆的调整，调整后继续之前的操作，直到交换的位置到达0为止，也就是
         * 堆大小一直减1减到0为止。此时，堆中的数据就变成了有序的数，而且是降序的。
         */
        public void sorted () {
            if (heap.length == 0) {
                throw new IllegalStateException("Heap Size is empty");
            }

            // 堆的大小
            int sortedIndex = heapSize;
            // 堆的大小没到0的时候，一直进行交换，堆调整操作
            while (sortedIndex > 0) {
                // 将0位置上的数据与最后位置上的数据进行交换，并且堆大小减1
                swap(heap, 0, --sortedIndex);
                // 交换后，进行堆调整
                afterSortefHeapfy(heap, 0, sortedIndex);
            }
        }

        /**
         * 将第一个位置上的数据和最后位置上的数据进行交换后，堆结构调整逻辑。
         * 按照排序的思想，将整个堆中第一个位置上的数据和最后一个位置上的数据进行交换后，有可能整个堆就不是大根堆或者小根堆。
         * 需要进行调整，重新将剩余的数据调整成大根堆或者小根堆。
         * @param heap 堆
         * @param index 0位置，从0位置开始向下不断的进行比较。
         * @param sortedIndex 堆的大小，没交换一次，堆的大小就减1
         */
        private void afterSortefHeapfy(int[] heap, int index, int sortedIndex) {
            // 对于堆来说，下标从0开始，那么左孩子下标为：2 * i + 1，右孩子下标为：2 * i + 2，父亲节点下标为：(i - 1) / 2.
            int leftIndex = index * 2 + 1;
            while (leftIndex < sortedIndex){

                if (flag) { // 大根堆
                    // 找左右孩子中比较大的那个数据的下标，因为大根堆要用左右孩子中最大的那个数据和父亲节点进行比较。
                    int largestIndex = leftIndex + 1 < sortedIndex && heap[leftIndex + 1] > heap[leftIndex] ? leftIndex + 1 : leftIndex;
                    // 左右孩子中大的那个数据和父亲节点进行比较，找到两者之间大的那个数据下标，
                    largestIndex = heap[index] > heap[largestIndex] ? index : largestIndex;
                    // 1、直到最后的节点，最后的节点没有左右孩子，比较的是时候也是自己和自己比较，此时退出，表示当前节点已经调整完毕。
                    // 2、直到最后的节点，左右孩子都没有比它自己大的数据了，此时退出，表示当前节点已经调整完毕。
                    if (index == largestIndex) {
                        break;
                    }
                    // 交换，将比较大的数据和父亲节点的位置的数据进行交换，较大的数据成为父亲节点。
                    swap(heap, index, largestIndex);
                    // 父亲节点的下标来到最大位置的数据的下标位置
                    index = largestIndex;
                    // 继续找新的父亲节点的左孩子进行处理
                    leftIndex = index * 2 + 1;
                } else { // 小根堆
                    int smallerIndex = leftIndex + 1 < sortedIndex && heap[leftIndex + 1] < heap[leftIndex] ? leftIndex + 1 : leftIndex;
                    smallerIndex = heap[index] < heap[smallerIndex] ? index : smallerIndex;
                    // 1、直到最后的节点，最后的节点没有左右孩子，比较的是时候也是自己和自己比较，此时退出，表示当前节点已经调整完毕。
                    // 2、直到最后的节点，左右孩子都没有比它自己小的数据了，此时退出，表示当前节点已经调整完毕。
                    if (index == smallerIndex) {
                        break;
                    }
                    // 交换，将比较小的数据和父亲节点的位置的数据进行交换，较小的数据成为父亲节点。
                    swap(heap, smallerIndex, index);
                    // 父亲节点的下标来到最小位置的数据的下标位置
                    index = smallerIndex;
                    // 继续找新的父亲节点的左孩子进行处理
                    leftIndex = index * 2 + 1;
                }
            }
        }

        /**
         * 单个插入数据后，对堆结构进行调整。
         * @param heap 堆
         * @param index 当前数据插入堆的索引下标
         */
        private void heapfy(int[] heap, int index) {
            if (flag) { // 大根堆
                // 大根堆逻辑调整，如果当前节点的父亲节点小于当前节点，当前节点需要来到父亲节点的位置，父亲节点来到当前节点的位置。
                while (heap[(index - 1) / 2] < heap[index]) {
                    // 调整，当前节点的父亲节点小于当前节点，当前节点需要来到父亲节点的位置，父亲节点来到当前节点的位置
                    swap(heap, index, (index - 1) / 2);
                    // 当前节点的索引来到其父亲节点的索引位置。
                    index = (index - 1) / 2;
                }
            } else { // 小根堆
                // 小根堆逻辑调整，如果当前节点的父亲节点大于当前节点，当前节点需要来到父亲节点的位置，父亲节点来到当前节点的位置。
                while (heap[(index - 1) / 2] > heap[index]) {
                    // 调整，当前节点的父亲节点大于当前节点，当前节点需要来到父亲节点的位置，父亲节点来到当前节点的位置
                    swap(heap, (index - 1) / 2, index);
                    // 当前节点的索引来到其父亲节点的索引位置。
                    index = (index - 1) / 2;
                }
            }

        }

        private void swap(int[] heap, int f, int index) {
            int temp = heap[f];
            heap[f] = heap[index];
            heap[index] = temp;
        }
    }

    /**
     * 对数器验证：思想，用java提供的工具类和我们自己写的算法对处理后的数组，
     * 进行每一个元素比对。
     */
    private static boolean logarithmizer(int[] arr, consumerHeap heap) {
        /**
         * java提供的工具类
         */
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != heap.poll()) {
                count++;
                return false;
            }
        }

        return true;
    }
}
